package com.hjx.other;

/**
 * 解析形如 A(B(C(,),),E(,)) 的字符串，在内存中构建一棵二叉树
 *
 *       A
 *     / |
 *    B  E
 *   /
 *  C
 * 说明：
 * 1. 是形如上面的字符串，你的程序需要能解析所有类似的字符串，而不是只限于上面这一个
 * 2. 逗号分隔为左右两个节点，节点可能为空
 * 3. 字符是节点里的值，括号里的是左右节点，为了简化节点值只会是一个字符
 */
public class ParseStringToBinaryTree {

    public Tree changeStruct(String string) {

        char[] chars = string.toCharArray();
        //分割字符
        //转换为树
        if (chars.length > 2 && chars[1] == '(' && chars[chars.length - 1] == ')') {
            Tree tree = new Tree(chars[0] + "");

            String nextString = string.substring(1, chars.length);
            char[] nextChars = nextString.toCharArray();
            int splitIndex = findSplitIndex(nextChars);

            String left = !nextString.contains("(") && !nextString.contains(")")? "" : nextString.substring(1, splitIndex);
            String right = !nextString.contains("(") && !nextString.contains(")") ? "" : nextString.substring(splitIndex + 1, nextString.length()-1);

            Tree leftSubTree = changeStruct(left);
            Tree rightSubTree = changeStruct(right);

            tree.setLeft(leftSubTree);
            tree.setRight(rightSubTree);
            return tree;
        } else {
            return null;
        }

    }

    public int findSplitIndex(char[] nextChars){
        int leftSize = 0;
        int splitIndex = 0;
        boolean first = true;
        for (int i = 1; i < nextChars.length-1; i++) {
            if(nextChars[i] == '(') {
                leftSize++;
            }
            if (nextChars[i] == ')') {
                leftSize--;
            }
            if (leftSize == 0 && !first) {
                splitIndex = i+1;
                break;
            }
            //处理(,)这种结构的字符串
            if (nextChars.length == 3) {
                splitIndex = i;
                break;
            }
            first = false;
        }
        return splitIndex;
    }

    public static void main(String[] args) {
        String a = "F(A(B(C(,),),E(,)),D(,))";
        Tree tree = new ParseStringToBinaryTree().changeStruct(a);

        System.out.println(tree);


    }
}

class Tree {

    String value;
    Tree left;
    Tree right;

    public Tree(String value) {
        this.value = value;
    }

    public Tree(Tree left, Tree right) {
        this.left = left;
        this.right = right;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public Tree getLeft() {
        return left;
    }

    public void setLeft(Tree left) {
        this.left = left;
    }

    public Tree getRight() {
        return right;
    }

    public void setRight(Tree right) {
        this.right = right;
    }
}